package leetcode.动态规划和贪心;

/**
 * 最小路径和
 *
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 分析：假设 dp[i][j] 代表的是 (i, j) 这个位置的最小路径和，所以 dp[i][j] 的值应该是一个累加的结果，
 *      由于每次只能向下或者向右移动一步，所以 dp[i][j] = Min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
 *
 *      那么状态转移方程就出来了，动态规划是基于已经算好的结果往下计算的，所以继续思考：有哪些值可以提前算好，以给
 *      接下来的其他计算使用？
 *
 *      因为只能往下、往右走，所以第一列和第一行只有一种走法，就是一直往下走或者一直往右走。
 *      基于此，我们可以得到第一行和第一列的各个 grid[i][j] 的值，这个值就是提前为了动态规划提前计算好的数据。
 *
 *      接下来遍历每一个格子，计算最小的 dp 值
 */
public class Test64最小路径和 {

    public static int minPathSum(int[][] grid) {
        int n = grid.length;     // 行
        int m = grid[0].length;  // 列
        if (m == 0 || n == 0) {
            return 0;
        }
        // 寻找左边界各点的路径总和
        for (int i = 1; i < n; i++) {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        // 寻找上边界各点的路径总和
        for (int j = 1; j < m; j++) {
            grid[0][j] = grid[0][j - 1] + grid[0][j];
        }
        // 推导内部各点的最小总步数
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[n - 1][m - 1];
    }

    public static void main(String[] args) {
        int[][] a = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(minPathSum(a));
    }
}
